package 经典问题;

/*
 * 回溯法：0-1背包问题
 * 
 * 题目大意
 * 背包问题，相信各位看官肯定都有所耳闻！笔者就在此简单的描述一下背包问题：
	给定一背包和n件物品，背包的容量为c，第i件物品的重量为w[i],价值为v[i]（1<=i<=n）;问装那些物品，可使得价值最大？
        思路分析：显然，每种物品不外乎两种选择：装入和不装入背包！若将装入用状态1表示，不装入用状态0表示；那么就可构成一个二叉树！一共有n层，所以就可通过从第一层开始遍历搜索，在装入的物品总重量不大于c的情况下，找到最优解了！
	
解题思路
	


* 问题分析：  
* 
	参考：http://blog.csdn.net/renshengkudaun/article/details/51048944
	@TODO:需要自己手写一遍
	@Date 2017-11-11 15：53

 */
public class Bag_Backtracking {
	
	private static final String TAG = "Bag_Backtracking";
	private int c = 10;
	private int[] w = {0, 2, 2, 6, 5, 5};			//索引0忽略
	private int[] v = {0, 6, 3, 5, 4, 6};
	private int[] x = new int[6];
	private int bestcp = 0;
	private int[] bestcpArr = new int[6];
	private int count = 0;
	private int n = 5;								//物品数量
	
	
	/**
	 * 
	 * @param i：查找到了第i个物品（i从1开始索引）
	 * @param cv：当前包中价值
	 * @param cw:当前包中重量
	 */
	public void backtracking(int i, int cw, int cv) {
		count ++;
		if (i > n) {
			if (cv > bestcp) {
				bestcp = cv;
				for (int j = 0; j < 6; j ++) {
					bestcpArr[j] = x[j];
				}
			}
		} else {
//			开始遍历，如果k=0，则表示不装下此物品，k=1，则表示装下此物品
			for (int k = 0; k <=1; k ++) {
				x[i] = k;
				if (cw+w[i] <= c) {
					cv += v[i]*k;
					cw += w[i]*k;
					backtracking(i+1, cw, cv);
					cv -= v[k]*k;					//回溯
					cw -= w[k]*k;
				}
			}
		}
	}
	public static void main(String[] args) {
		new Bag_Backtracking().backtracking(1,0,0);
	}
}
